package com.klun.project.common.constans.leetcode;

import com.klun.project.common.constans.utils.ParseUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

//给定一个字符串 s 和一个字符串字典 wordDict ，在字符串 s 中增加空格来构建一个句子，
// 使得句子中所有的单词都在词典中。以任意顺序 返回所有这些可能的句子。
// 注意：词典中的同一个单词可能在分段中被重复使用多次。
//
// 示例 1：
//输入:s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
//输出:["cats and dog","cat sand dog"]
//
// 示例 2：
//输入:s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
//输出:["pine apple pen apple","pineapple pen apple","pine applepen apple"]
//解释: 注意你可以重复使用字典中的单词。
//
// 示例 3：
//输入:s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
//输出:[]
//
// 提示：
// 1 <= s.length <= 20
// 1 <= wordDict.length <= 1000
// 1 <= wordDict[i].length <= 10
// s 和 wordDict[i] 仅有小写英文字母组成
// wordDict 中所有字符串都 不同
// Related Topics 字典树 记忆化搜索 哈希表 字符串 动态规划 回溯
// 👍 644 👎 0

public class Solution140 {

	public List<String> wordBreak(String s, List<String> wordDict) {
		HashSet<String> wds = new HashSet<>(wordDict);
		List<String> res = new ArrayList<>();
		int length = s.length();
		boolean[][] dp = new boolean[length + 1][length + 1];
		dp[0][0] = true;
		for (int i = 1; i < s.length() + 1; i++) {
			for (int j = 0; j < i; j++) {
				if (wds.contains(s.substring(j, i))) {
					dp[j][i] = true;
				}
			}
		}
		dfs(res, 0, s.length(), dp, new StringBuilder(), s);
		return res;
	}

	public void dfs(List<String> res, int begin, int len, boolean[][] dp, StringBuilder sb, String s) {
		if (begin == len) {
			res.add(String.valueOf(sb));
			return;
		}
		int end = sb.length();
		for (int i = begin; i < len; i++) {
			if (dp[begin][i + 1]) {
				if (end ==0){
					sb.append(s.substring(begin, i + 1));
				}else {
					sb.append(" " + s.substring(begin, i + 1));
				}

				dfs(res, i + 1, len, dp, sb, s);
				sb = new StringBuilder(sb.substring(0, end));
			}
		}
	}

	public static void main(String[] args) {
		Solution140 solution = new Solution140();
		List<List<Integer>> arrayLists = ParseUtils.stringToIntLists("[[2],[3,4],[6,5,7],[4,1,8,3]]");
		System.out.println(solution.wordBreak("catsanddog", Arrays.asList("cat", "cats", "and", "sand", "dog")));
		System.out.println(solution.wordBreak("pineapplepenapple", Arrays.asList("apple", "pen", "applepen", "pine", "pineapple")));
	}

}
